package com.gitee.feizns.explore.data_structure.union_find;

/**
 * 1319. 连通网络的操作次数
 * @author feizns
 * @since 2020/3/13
 */
public class MakeConnected {

    //12
    //[[1,5],[1,7],[1,2],[1,4],[3,7],[4,7],[3,5],[0,6],[0,1],[0,4],[2,6],[0,3],[0,2]]
    static int[][] r = new int[][]{ {1, 5}, {1, 7}, {1, 2}, {1, 4}, {3, 7}, {4, 7}, {3, 5}, {0, 6}, {0, 1}, {0, 4}, {2, 6}, {0, 3}, {0, 2} };
    public static void main(String[] args) {
        int connected = makeConnected(12, r);
        System.out.println(connected);
    }

    public static int makeConnected(int n, int[][] connections) {
        Uf uf = new Uf(n);
        for (int[] con : connections)
            uf.union(con[0], con[1]);
        return uf.redundancy >= uf.count - 1 ? uf.count - 1 : -1;
    }

    static class Uf {
        int[] parents;
        int count;
        int redundancy;
        Uf(int size) {
            parents = new int[size];
            for (int i = 0; i < size; i++)
                parents[i] = i;
            count = size;
        }
        void union(int q, int p) {
            int qr = find(q);
            int pr = find(p);
            if ( qr != pr ) {
                parents[qr] = pr;
                count--;
            } else
                redundancy++;
        }
        int find(int q) {
            if ( q != parents[q] )
                parents[q] = find(parents[q]);
            return parents[q];
        }
    }

}
